package com.shm.leetcode;

/**
 * 50. Pow(x, n)
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：x = 2.00000, n = 10
 * 输出：1024.00000
 * 示例 2：
 *
 * 输入：x = 2.10000, n = 3
 * 输出：9.26100
 * 示例 3：
 *
 * 输入：x = 2.00000, n = -2
 * 输出：0.25000
 * 解释：2-2 = 1/22 = 1/4 = 0.25
 *
 *
 * 提示：
 *
 * -100.0 < x < 100.0
 * -231 <= n <= 231-1
 * -104 <= xn <= 104
 *
 * @author SHM
 */
public class MyPow {
    /**
     * 方法二：快速幂迭代
     * 找规律发现，幂次数n的二进制中为1时，结果乘上对应的cur_x
     * 对cur_x自身不断进行平方，从x,x^2,x^4,x^8,....
     * 当times最低位为1时，结果乘上对应的cur_x
     * 举例：x^13
     * 幂次数的二进制为1101，即 x^1 * x^4 * x^8 = x^13
     *
     * 作者：二货磁铁
     * 链接：https://leetcode-cn.com/leetbook/read/programmation-efficace/9bl7w3/?discussion=LT5GhQ
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        /**
         * 执行结果：
         * 解答错误
         * 显示详情
         * 输入：
         * 2.00000
         * -2147483648
         * 输出：
         * 1.00000
         * 预期结果：
         * 0.0
         *
         * 负数越界，需转为 long
         */
        long t=n;
        //如果说n小于零，那么就求x的倒数的正n次方
        return t>=0?powHelp(x,t):1.0/powHelp(x,-t);
    }

    double powHelp(double x,long t){
        double ans = 1.0;
        double curX = x;
        while(t>0){
            if(t%2==1){
                ans*=curX;
            }
            curX *=curX;
            t/=2;
        }
        return ans;
    }
}
